package algotithm.weekendrace.leetcode237.test3;

import java.util.*;

/**
 * @author zhouyanxiang
 * @Date 2021-04-2021/4/18-10:23
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] tasks = {{1,2},{2,4},{3,2},{4,1}};
//        int[][] tasks = {{7,10},{7,12},{7,5},{7,4},{7,2}};
        int[] order = solution.getOrder(tasks);
        for (int i : order) {
            System.out.print(i + " ");
        }
    }

    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        for(int i = 0; i < n; i++) {
            tasks[i] = new int[]{tasks[i][0], tasks[i][1], i};
        }
        Arrays.sort(tasks, (t1, t2) -> t1[0] != t2[0] ? t1[0] - t2[0] : t1[1] != t2[1] ? t1[1] - t2[1] : t1[2] - t2[2]);
        PriorityQueue <int[]> pq = new PriorityQueue<>( (p1, p2) -> (p1[1] != p2[1] ? p1[1] - p2[1] : p1[2] - p2[2]));
        int[] res = new int[n];
        long time = 0;
        int ind = 0;
        for(int i = 0; i < n; i++) {
            if(pq.isEmpty()) {
                pq.add(tasks[ind]);
                time = tasks[ind++][0];
            }
            int[] tmp = pq.poll();
            time += tmp[1];
            while(ind < n && tasks[ind][0] <= time) {
                pq.add(tasks[ind++]);
            }
            res[i] = tmp[2];
        }
        return res;
    }
}
